package experiment3;

import java.util.*;

public class Graph<T> {
    private int size; // 图的大小（图中最多能有多少个顶点）
    private static int[][] edge; // 邻接矩阵，用于储存边的关系
    private ArrayList<T> vtxName; // the names of vertexes.
    private boolean[] visited; // 来标识顶点是否已经访问
    private boolean hasCycle;//true代表有环
    private Set<T> set;


    /**
     * 初始化操作
     *
     * @param size
     */
    public void initializedWithSize(int size) {
        this.size = size;
        edge = new int[size][size];
        vtxName = new ArrayList<>(size);
        visited = new boolean[size];
        set = new HashSet<>();
        resetVisitedArray();
    }


    /**
     * 将标识顶点数组重新初始化
     */
    public void resetVisitedArray() {
        for (int i = 0; i < size; i++) {
            visited[i] = false;
        }
    }

    /**
     * 增加顶点
     */
    public void addVertex(T v) {
        vtxName.add(v);
    }

    /**
     * @param from 起始顶点
     * @param to   终点
     * @return
     */
    public int addEdge(T from, T to) {
        // u,v对应的是顶点列表的下标
        int u, v;
        u = vtxName.indexOf(from);
        v = vtxName.indexOf(to);
        // 看这两个顶点是否收录在vtxName
        if (v == -1 || u == -1) {
            return -1;
        }
        // 如果有重复则直接覆写，1值代表度
        edge[u][v] = 1;
        return 0;

    }

    // 递归
    public void dfs(int start, ArrayList<T> vtxsList, ArrayList<T> dfsVtxs) {
        // 不存在的话直接返回
        if (vtxName.get(start) == null) {
            return;
        }
        // 获取对应下标的顶点值
        if (!visited[start]) {
            visited[start] = true;
            vtxsList.add(vtxName.get(start));
            set.add(vtxName.get(start));
        }

        for (int i = 0; i < edge.length; i++) {
            dfsVtxs.add(vtxName.get(i));
            if (edge[start][i] == 1) {
                if (!visited[i]) {
                    dfs(i, vtxsList, dfsVtxs);
                }

                if (set.contains(vtxName.get(i))) hasCycle = true;
            }
        }

        set.remove(vtxName.get(start));
    }



   public ArrayList<T> topLogical(){
        if (hasCycle) {
            System.out.println("有环，不能拓扑排序！！！");
            return null;
        }

       ArrayList<T> entStack = new ArrayList<>();
       ArrayList<T> outStack = new ArrayList<>();
       ArrayList<T> vtxsList = new ArrayList<>();
       nonRecursiveDFS(0, vtxsList, entStack, outStack);
       return outStack;
   }

   public boolean hasCycle(){
        return hasCycle;
   }

    //非递归
    public void nonRecursiveDFS(int start, ArrayList<T> vtxsList, ArrayList<T> entStack , ArrayList<T> outStack) {
        // 用一个栈维护
        Deque<T> deque = new LinkedList<>();

        // 不存在的话直接返回
        if (vtxName.get(start) == null) {
            return;
        }
        // 获取对应下标的顶点值
        if (!visited[start]) {
            visited[start] = true;
            vtxsList.add(vtxName.get(start));
            deque.addFirst(vtxName.get(start));
            entStack.add(vtxName.get(start));
        }
        while(!deque.isEmpty()){
            int count = 0;
            // 获取当前栈顶顶点
            T curVtx = deque.peekFirst();
            int curInx = vtxName.indexOf(curVtx);

            for (int i = 0; i < edge.length; i++) {
                if (edge[curInx][i] == 1) {
                    if (!visited[i]) {
                        visited[i] = true;
                        T temp = vtxName.get(i);
                        vtxsList.add(temp);
                        // 如果有通路，且通路的终点未访问过，将顶点压入栈，并记录入栈顺序
                        deque.addFirst(temp);
                        entStack.add(temp);
                        break;
                    }
                }
                count++;
            }
            // 如果邻接节点都访问过了则可以丢了
            if(count == edge.length){
                outStack.add(deque.pollFirst());
            }
        }
    }
}
